package algorithm.bin_tree.depthtraverse;

import algorithm.bin_tree.BinTree;
import algorithm.bin_tree.Node;

import java.util.List;
import java.util.Stack;

/**
 * @program: util
 * @description: 中根遍历
 * @author: zhouliangliang
 * @create: 2021-06-04 20:03
 **/
public class MiddleRootDepthTraverse {

    /**
     * 非递归中跟遍历
     */

    private void middleRootTraverseUseStack(Node root) {
        Stack<Node> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.leftChild;
            }

            if(!stack.isEmpty()) {
                Node node = stack.pop();
                System.out.println(node.data);
                root = node.rightChild;
            }
        }
    }

    private void middleRootRecusion(Node root) {
        if(root == null) {
            return;
        }
        middleRootRecusion(root.leftChild);
        System.out.println(root.data);
        middleRootRecusion(root.rightChild);
    }

    public static void main(String[] args) {
        BinTree tree = new BinTree();
        int[] array = new int[]{1,2,3,4,5,6,7};
        List<Node> list = tree.createBinTree(array);

        MiddleRootDepthTraverse mrt = new MiddleRootDepthTraverse();
        mrt.middleRootTraverseUseStack(list.get(0));

        System.out.println();
        mrt.middleRootRecusion(list.get(0));

    }
}
